\section{Problema 1}

\subsection{Introducci\'on}


Un arreglo est\'a ordenado de manera no decreciente, si el mismo est\'a ordenado de manera creciente no estricta. Esto implica, que dicho arreglo, tiene elementos ordenados de forma creciente, aunque permite elementos repetidos. Por otro lado, se define \textit{meseta} de un arreglo, a un subarreglo del mismo, tal que todos los elementos en dicho subarreglo son iguales.\\
El enunciado del primer ejercicio pide, dados 2 arreglos ordenados de manera no decreciente, dar la máxima meseta, del arreglo resultante de combinar ambos arreglos en un único arreglo, tal que este tambien est\'e ordenado en forma no decreciente.


	   
\subsection{Desarrollo}

Para resolver el problema, se asume que los dos arreglos est\'an ordenados no decrecientemente. Se decide combinar ambos arreglos, de manera similar a como lo realiza el algoritmo \textit{Mergesort} en la etapa en que ambos subarreglos se funden (etapa de Merge). Esto es realizado por el m\'etodo \textbf{unirOrdenados}. El algoritmo comienza inspeccionando las posiciones iniciales de ambos arreglos, ubicando el menor elemento entre los dos, y copi\'andolo al arreglo resultante. Se procede a inspeccionar el siguiente elemento del arreglo que conten\'ia el elemento previamente agregado y a compararlo nuevamente con el menor elemento del otro arreglo. De esta manera se recorre ambos arreglos hasta insertar cada uno de los elementos, en el nuevo arreglo resultante.\\

 Una vez simplificados ambos arreglos en un único arreglo tal que cumple la condici\'on de ser no decreciente, se procede a buscar la m\'axima meseta (m\'etodo \textbf{buscarMesetaMaxima}). Simplemente se recorre el arreglo, comparando los elementos contiguos del arreglo, detectando mesetas, y manteniendo un \textit{backup(respaldo)} de la mayor meseta computada hasta el momento. Al final de la inspecci\'on del arreglo se puede informar satisfactoriamente la mayor meseta contenida en el vector.\\



\newpage

\subsection{Pseudoc\'odigo}
En el archivo \textbf{Ej1.java} podremos encontrar la clase ``Ej1'' con las funciones \textit{unirOrdenados}
y \textit{buscarMesetaMaxima}.

\begin{parr}
\begin{algorithm}[H]
\caption{\operL{unirOrdenados}{ \vin{array\_a}{array de ints}, \vin{array\_b}{array de ints}, \vin{size\_a}{int},
\vin{size\_b}{int}}{array}} \begin{algorithmic}[1]\parskip=1mm
\STATE   \textbf{var} array\_res de longitud size\_a + size\_b
%\FOR{primera posición de array\_res hasta la última}
\STATE   \textbf{var} punt\_b $\leftarrow$ 0 // \textit{0 es la primera posición de los arreglos}
\STATE   \textbf{var} punt\_a $\leftarrow$ 0 
\FOR{i = 0 \textbf{hasta} longitud(array\_res) - 1 }
	\IF{ya miré todos los elementos del array\_a}
		\STATE array\_res[i] $\leftarrow$  array\_b[punt\_b]
		\STATE punt\_b $\leftarrow$ punt\_b +1
	\ELSE
		\STATE \COMMENT{sigo por acá si me quedan elementos del array\_a por analizar}
		\IF{ya miré todos los elementos del array\_b}
			\STATE array\_res[i] $\leftarrow$  array\_a[punt\_a]
			\STATE punt\_a $\leftarrow$ punt\_a +1
		\ELSE
			\STATE \COMMENT{me quedan elementos por revisar en ambos arreglos}
			\IF{array\_b[punt\_b] $<$ array\_a[punt\_a]}
				\STATE array\_res[i] $\leftarrow$  array\_b[punt\_b]
				\STATE punt\_b $\leftarrow$ punt\_b +1
			\ELSE
				\STATE \COMMENT{el elemento apuntado en array\_a es menor al de array\_b}
					\STATE array\_res[i] $\leftarrow$  array\_a[punt\_a]
					\STATE punt\_a $\leftarrow$ punt\_a +1
			\ENDIF
		\ENDIF
	\ENDIF 
\ENDFOR
\STATE return array\_res

\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operL{buscarMesetaMaxima}{ \vin{array}{array de ints}, \vin{size}{int}}{array}}
\begin{algorithmic}[1]\parskip=1mm
% \caption{\operL{buscarMeseta}{ \vin{array}{array de ints}, \vin{size}{int}}{int}} \begin{algorithmic}[1]\parskip=1mm

\STATE \textbf{var} meseta\_MAX $\longleftarrow$ 0
\STATE \textbf{var} meseta\_actual $\longleftarrow$ 0
\STATE \textbf{var} ultimo\_num $\longleftarrow$ array[0]
\FOR{i desde 0 hasta tamaño de array}
\IF{ultimo\_num es igual a array[i]}
	\STATE meseta\_actual $\longleftarrow$ meseta\_actual + 1
\ELSE
	\STATE \COMMENT{terminó la meseta temporaria}
	\IF{meseta\_actual $>$ meseta\_max}
		\STATE meseta\_max $\longleftarrow$ meseta\_actual
	\ENDIF
	ultimo\_num $\longleftarrow$ array[i]
	meseta\_actual $\longleftarrow$ 1
\ENDIF
\ENDFOR
\STATE \COMMENT{agregamos el siguiente if por si la meseta} 
\STATE \COMMENT{estaba al final del arreglo y sale del for sin actualizar}
\IF{meseta\_actual $>$ meseta\_max}
		\STATE meseta\_max $\longleftarrow$ meseta\_actual
	\ENDIF
\STATE return meseta\_max
\end{algorithmic}
\end{algorithm}
\end{parr}

\newpage

\subsection{Complejidad}
 La complejidad del algoritmo consiste en 2 funciones iterativas con un
 simple ciclo en cada una. En \textit{unirOrdenados} el ciclo recorrerá siempre la longitud del nuevo arreglo creado que
 sería la suma entre las longitudes de los arreglos pasados como parámetro. El ciclo mencionado es lo único que afectaría
 a la complejidad asintótica de la primera función, ya que lo demás, adentro y afuera del ciclo, es de complejidad
 constante. \\
 En el segundo algoritmo pasaría algo similar. Tenemos un ciclo que recorre  el arreglo pasado como parámetro (que en
 nuestro caso sería el arreglo formado por la función  \textit{unirOrdenados}) y lo demás son instrucciones de
 complejidad constante.

 
\begin{center}
    \begin{tabular}{ | p{17cm} |}
	\hline
	Sean \textbf{X} e \textbf{Y} los arreglos recibidos en el archivo de entrada. 
	\begin{itemize}
	  \item \textit{unirOrdenados}: recorrer el nuevo arreglo llevaría complejidad \textbf{O($|$X$|$+$|$Y$|$)}
	  \item \textit{buscarMesetaMaxima}: recorrer el arreglo, teniendo en cuenta que es el mismo arreglo que en \textit{unirOrdenados}
		también llevaría complejidad  \textbf{O($|$X$|$+$|$Y$|$)}. 
	\end{itemize}
	Entonces:
	\textbf{O($|$X$|$+$|$Y$|$)} + \textbf{O($|$X$|$+$|$Y$|$)} $\in$ \textbf{O($|$X$|$+$|$Y$|$)}
	Por lo que concluimos que la complejidad asintótica del algoritmo que resuelve el ejercicio 1 es: \\ 
	\textbf{O($|$X$|$+$|$Y$|$)}
	 \\ \hline
    \end{tabular}
\end{center}

 O sea, en otras palabras, la complejidad \textbf{asintótica} siempre será la misma: \textbf{O($|$X$|$+$|$Y$|$)}, no importa las instancias. En otras palabras, el caso promedio es igual al peor caso y al mejor caso.


\subsection{Tests}
Como mencionamos antes, el algoritmo es muy simple y en nuestra opinión no presenta demasiadas dificultades: va a
recorrer siempre todos los elementos de los 2 arreglos, en el caso de unirOrdenado, y todo el arreglo, en el caso de
buscarMesetaMaxima; y en ambos casos no hace nada más interesante que varíe entre diferentes instancias. Es por esto que
pensamos que no existen familias de casos que puedan llegar a ser demasiado complejas de ejecutar.
Sin embargo, decidimos hacer tests de diferentes familias que podrían llegar a parecer ``interesantes'' a primera vista.
	\begin{itemize}
	  \item \textbf{Todos elementos iguales}: ambos arreglos de entrada contienen el mismo elemento
	  \item \textbf{Sin repetidos}: los arreglos no tienen el mismo elemento dos veces y tampoco comparten algún elemento
	  entre ellos.
	\end{itemize}

\subsection{Gr\'aficos}

%\begin {figure} [H]
%\begin {center}
%\includegraphics[width=12cm]{./graficos/Grafico-sinRepetidos.png}
%\caption{Muestra el rendimiento segun las intrucciones en funcion del tamaño de la entrada, en este caso particular, para sinRepetidos}
%\end {center}
%\end{figure}
%
%
%\begin {figure} [H]
%\begin {center}
%\includegraphics[width=12cm]{./graficos/Grafico-todosIguales.png}
%\caption{Muestra el rendimiento segun las intrucciones en funcion del tamaño de la entrada, en este caso particular, para todosIguales}
%\end {center}
%\end{figure}



\begin{figure}[H]
\centering
\epsfig{file=./graficos/sinRepetidos-vs2nFINAL-jpg.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Sin Repetidos}
\label{fig:sin-repet}
\end{figure}

\begin{figure}[H]
\centering
\epsfig{file=./graficos/todosIguales-vs2nFINAL-jpg.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Todos Iguales}
\label{fig:sin-repet}
\end{figure}

Para analizar lo obtenido, decidimos compararlo con la función \textbf{2*n}. Hicimos esto para demostrar que nuestro algoritmo tardaba tiempo \textbf{O(n)}. Elegimos particularmente 2*n porque al analizar estadísticamente los valores, nos dimos cuenta que era la mejor opción ya que crecen particularmente igual. Para obtener los gráficos tomamos como el tamaño de entrada la suma de las longitudes de ambos arreglos y contábamos cada vez que pasaba por los fors de ambas funciones.

Claramente, cumplimos con la complejidad asintótica previamente declarada: todos los valores de tiempo de nuestro algoritmo se sobreponen con los valores de la función dada para comparar (en este caso 2*n).  

No obstante, decidimos agregar un gráfico más demostrando que existe ``mini peor caso''. Decimos esto porque hay familias de instancias donde hay una diferencia de \textbf{n} iteraciones, con n siendo la suma de ambas longitudes de los arreglos. Es decir, existen instancias a que comparadas con las instancias b, la complejidad de las primeras es la complejidad de las segundas sumadas a n. Aunque esto no influya en la complejidad asintótica, decidimos remarcarlo porque nos pareció interesante.

Para este nuevo test, al necesitar mayor exactitud, contamos además las ejecuciones de los diferentes ifs de las funciones principales de nuestro algoritmo.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/Grafico-Comparacion-png-jpg.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Todos Iguales}
\label{fig:sin-repet}
\end{figure}

En este grafico mostramos como var\'ia la cantidad de instrucciones que hace el algoritmo para los distintos casos.
Para enriquecer un poco lo mostrado, comparamos la cantidad de instrucciones en funci\'on del tamaño de la entrada y no la cantidad de veces que se itera, ya que siempre se va a iterar todo el vector por como pensamos el algoritmo.

Claramente la ejecuci\'on de \textit{sinRepetidos} tiene un crecimiento mayor a la ejecución de \textit{todosIguales}. Era esto a lo que nos referíamos sobre "mini peor caso". Aunque tengan mayor crecimiento, la diferencia es asintóticamente despreciable y ambas familias de instancias pertenecerían a O(n).

\subsection{Conclusiones}
En conclusión, el problema no fue muy sorprendente ya que el algoritmo que usamos para resolverlo estaba compuesto
simplemente por \textit{fors} e \textit{ifs} y ninguna complicación. \\
Los tests confirmaron nuestras predicciones sobre la simplicidad del algoritmo y no mostraron ningún tipo de
\textit{outlier}.



